/**
 * 
 */
package process.models;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Properties;
import java.util.Vector;

import process.PreProcess;

import data.Distance;
import data.EuclideanDistance;
import data.SimilaritySet;

/**
 * Cluster ensemble employs a number of clusterer to enhance the robust and accuracy of the cluster.
 * @author yexijiang
 * @date Jul 15, 2008
 */
public class ClusterEnsemble 
{

	private SimilaritySet m_Set;
	private Vector<String> m_Labels;
	private Vector<Clusterer> m_Clusters;
	private int m_NumOfElements;	//	the number of the elements
	private int m_Sequence[];
	
	private Vector<String>[][] m_ClusteringClusters;	//	the clusters for each clusterer
	private double m_WeightMatrix[][];
	
	private int m_EnsembleClusterNumber;
	private Vector<String>[] m_EnsembleClusters;	//	final clusters
	
	
	public ClusterEnsemble(SimilaritySet set, int sequence[], Vector<String> labels, int numOfEnsembleCluster)
	{
		m_Set = set;
		m_Sequence = sequence;
		m_Labels = labels;
		m_Clusters = new Vector<Clusterer>();
		m_Clusters = new Vector<Clusterer>();
		m_NumOfElements = set.size();
		m_WeightMatrix = new double[m_NumOfElements][m_NumOfElements];
		m_EnsembleClusterNumber = numOfEnsembleCluster;
		m_EnsembleClusters = new Vector[numOfEnsembleCluster];
		
		for(int i = 0; i < m_EnsembleClusters.length; ++i)
		{
			m_EnsembleClusters[i] = new Vector<String>();
		}
		
		for(int i = 0; i < m_NumOfElements; ++i)
		{
			for(int j = 0; j < m_NumOfElements; ++j)
			{
				m_WeightMatrix[i][j] = 0;
			}
		}
	}
	
	public int clusteringSize()
	{
		return m_Clusters.size();
	}
	
	public void addClusterer(Clusterer clusterer)
	{
		m_Clusters.add(clusterer);
	}
	
	public Clusterer getClusterer(int index)
	{
		return m_Clusters.get(index);
	}
	
	public Vector<String>[] doEnsemble()
	{
		doClustering();
		return ensembleClusters();
	}
	
	private void doClustering()
	{
		m_ClusteringClusters = new Vector[m_Clusters.size()][((KMeans)m_Clusters.get(0)).getClusterNumber()];
		for(int i = 0; i < m_Clusters.size(); ++i)
		{
			m_ClusteringClusters[i] = m_Clusters.get(i).doClustering();
		}
		
//		calculateCoassociationMatrixByAccumulation();
		calculateCoassociationMatrixByConsensucFunction();
	}
	
	private void calculateCoassociationMatrixByAccumulation()
	{
		for(int i = 0; i < m_Clusters.size(); ++i)
		{
			int clusterNumber = m_ClusteringClusters[i].length;
			int matrix[][] = new int[m_NumOfElements][clusterNumber];
			for(int j = 0; j < m_NumOfElements; ++j)
			{
				for(int k = 0; k < clusterNumber; ++k)
				{
					matrix[j][k] = 0;
				}
			}
			for(int j = 0; j < clusterNumber; ++j)
			{
				for(int k = 0; k < m_ClusteringClusters[i][j].size(); ++k)
				{
					String label = m_ClusteringClusters[i][j].get(k);
					matrix[m_Set.getIndexByLabel(label)][j] = 1;
				}
			}
			
			//	output test
			/*System.out.println("For " + i + "th matrix:");
			System.out.print("Cluster:");
			for(int j = 0; j < clusterNumber; ++j)
			{
				System.out.print(j + "\t");
			}
			System.out.println();
			for(int j = 0; j < m_NumOfElements; ++j)
			{
				System.out.print(m_Labels.get(j) + "\t\t");
				for(int k = 0; k < clusterNumber; ++k)
				{
					System.out.print( + matrix[j][k] + "\t");
				}
				System.out.println();
			}
			*/
			
			//	initialize similarity matrix of each clusterer
			double simMatrix[][] = new double[m_NumOfElements][m_NumOfElements];
			

			for(int j = 0; j < matrix[0].length; ++j)
			{
				for(int k = 0; k < matrix.length; ++k)
				{
					if(matrix[k][j] != 1)
						continue;
					for(int l = 0; l < matrix.length; ++l)
					{
						simMatrix[k][l] += matrix[l][j];
					}
				}
			}
			
			//	add to m_WeightMatrix
			for(int j = 0; j < simMatrix.length; ++j)
			{
				for(int k = 0; k < simMatrix[j].length; ++k)
				{
					m_WeightMatrix[j][k] += simMatrix[j][k];
				}
			}
			
			//	output test
			/*System.out.println();
			for(int j = 0; j < simMatrix.length; ++j)
			{
				for(int k = 0; k < simMatrix.length; ++k)
				{
					System.out.print(simMatrix[j][k] + " ");
				}
				System.out.println();
			}*/
		}
		
		//	output test
		for(int j = 0; j < m_WeightMatrix.length; ++j)
		{
			for(int k = 0; k < m_WeightMatrix[j].length; ++k)
			{
				System.out.print(m_WeightMatrix[j][k] + " ");
			}
			System.out.println();
		}
	}
	
	
	private void calculateCoassociationMatrixByConsensucFunction()
	{
		for(int i = 0; i < m_NumOfElements; ++i)
		{
			String a = m_Labels.get(i);
			for(int j = 0; j < m_NumOfElements; ++j)
			{
				String b = m_Labels.get(j);
				m_WeightMatrix[i][j] = similarity(a, b);
			}
		}
		
		// normalize and get complement
		for(int i = 0; i < m_NumOfElements; ++i)
		{
			for(int j = 0; j < m_NumOfElements; ++j)
			{
				String b = m_Labels.get(j);
				m_WeightMatrix[i][j] = 1 - m_WeightMatrix[i][j] / (m_Clusters.size() + 1);
//				m_WeightMatrix[i][j] = m_WeightMatrix[i][j] / (m_Clusters.size() + 1);
			}
		}
		
		//	output test
/*		for(int j = 0; j < m_WeightMatrix.length; ++j)
		{
			for(int k = 0; k < m_WeightMatrix[j].length; ++k)
			{
				System.out.print(m_WeightMatrix[j][k] + " ");
			}
			System.out.println();
		}*/
	}
	
	//	calculate the similarity between two tags by the sum of kronecker delta function
	private double similarity(String x, String y)
	{
		int score = 0;
		
		for(int i = 0; i < m_Clusters.size(); ++i)
		{
			score += kronecker(x, y, i);
		}
		
		return score;
	}
	
	//	calculate the kronecker delta function of two elements
	private double kronecker(String x, String y, int clusteringIndex)
	{
		Vector<String>[] clusters = m_ClusteringClusters[clusteringIndex];
		//	find x and y in the same clusters
		for(int i = 0; i < clusters.length; ++i)
		{
			Vector<String> cluster = clusters[i];
			if(cluster.contains(x) && cluster.contains(y))
			{
				return 1;
			}
		}
		return 0;
	}
	
	//	re-clustering the weight matrix
	private Vector<String>[] ensembleClusters()
	{
		//	use the MST algorithm to create minimum spanning tree

		class Pair	<K, V>
		{
			private K first;
			private V second;
			
			public Pair(K key, V value)
			{
				first = key;
				second = value;
			}
			
			public K getFirst()
			{
				return first;
			}

			public void setFirst(K first)
			{
				this.first = first;
			}

			public V getSecond()
			{
				return second;
			}

			public void setSecond(V second)
			{
				this.second = second;
			}

			@Override
			public boolean equals(Object obj)
			{
				Pair<K, V> other = (Pair<K, V>)obj;
				if(first.equals(other.first) && second.equals(other.second))
					return true;
				return false;
			}
			
		}
		
		class PairCompare implements Comparator
		{

			public int compare(Object arg0, Object arg1)
			{
				Pair<String, Double> p1 = (Pair<String, Double>)arg0;
				Pair<String, Double> p2 = (Pair<String, Double>)arg1;
				if( 0 == p1.getSecond() - p2.getSecond())
					return 0;
				else if( 0 < p1.getSecond() - p2.getSecond())
					return 1;
				else
					return -1;
			}
			
		}
		
		final String NIL = new String("NIL");
		final double MAX = 2;
		PairCompare compare = new PairCompare();
		PriorityQueue<Pair<String, Double>> q = null;
		Vector<Pair<String, Double>> vkeys = null;
		Vector<Pair<String, String>> vparents = null;

		q = new PriorityQueue<Pair<String, Double>>(m_Labels.size(), compare);

		// key(u) is the minimum weight of any edge connecting v to a vertex in
		// the tree
		vkeys = new Vector<Pair<String, Double>>();
		// the default parent
		vparents = new Vector<Pair<String, String>>();

		for (int i = 0; i < m_Labels.size(); ++i) {
			Pair<String, Double> key = new Pair<String, Double>(
					m_Labels.get(i), 2.0);
			Pair<String, String> parent = new Pair<String, String>(m_Labels
					.get(i), NIL);
			vkeys.add(key);
			vparents.add(parent);
		}

		// put the root
		vkeys.get(0).setSecond(0.0);

		for (int i = 0; i < m_Labels.size(); ++i) {
			q.add(vkeys.get(i));
		}

		while (!q.isEmpty()) 
		{
			Pair<String, Double> u = q.poll();
			String label1 = u.getFirst();
			int index = m_Labels.indexOf(label1);

			for (int i = 0; i < m_Labels.size(); ++i) 
			{
				// for each v belongs to adj[u]
				if (i != index && m_WeightMatrix[index][i] < 1.0) 
				{
					// if v belongs to q and w(u,v) < key[v]
					Pair<String, Double> v = vkeys.get(i);
					if (q.contains(v)
							&& m_WeightMatrix[index][i] < v.getSecond()) 
					{
						Pair<String, Double> key = vkeys.get(i);
						q.remove(vkeys.get(i));
						key.setSecond(m_WeightMatrix[index][i]);
						vkeys.set(i, key); // key[v] <- w(u, v)
						q.add(key);

						Pair<String, String> parent = vparents.get(i);
						parent.setSecond(label1); // p[v] <- u
						vparents.set(i, parent);
					}
				}
			}
		}

		int num = 0;
		for (int i = 0; i < vparents.size(); ++i) {
			if (vparents.get(i).getSecond().equals(NIL)) {
				++num;
			}
		}
		
		int numOfCluster = 0;
		for(int i = 0; i < vparents.size(); ++i)
		{
			if(vparents.get(i).getSecond().equals(NIL))
				++numOfCluster;
		}
		
		//	decompose the forrest
		if(numOfCluster > m_EnsembleClusterNumber)
			System.out.println("Original cluster is more than ensemble cluster number.");
		while(numOfCluster < m_EnsembleClusterNumber)
		{
			int largestIndex = 0;
			double largestWeight = 0;
			for(int i = 0; i < vkeys.size(); ++i)
			{
				if(!vparents.get(i).getSecond().equals(NIL))	//	has parent
				{
					double weight = vkeys.get(i).getSecond();
					if(weight > largestWeight)
					{
						largestWeight = weight;
						largestIndex = i;
					}
				}
			}
			Pair<String, Double> key = vkeys.get(largestIndex);
			key.setSecond(2.0);
			vkeys.set(largestIndex, key);
			Pair<String, String> parent = vparents.get(largestIndex);
			parent.setSecond(NIL);
			vparents.set(largestIndex, parent);
			++numOfCluster;
		}
		
		Vector<String>[] clusters = new Vector[m_EnsembleClusterNumber];
		for(int i = 0; i < clusters.length; ++i)
		{
			clusters[i] = new Vector<String>();
		}
		
		//	put root into each cluster
		int n = 0;  
		for(int i = 0; i < vparents.size(); ++i)
		{
			if(vparents.get(i).getSecond().equals(NIL))
			{
				clusters[n++].add(vparents.get(i).getFirst());
			}
		}
		
		for(int i = 0; i < vparents.size(); ++i)
		{
			//	add non-root elements
			if(!vparents.get(i).getSecond().equals(NIL))
			{
				String current = vparents.get(i).getFirst();
				//	find the parent's pair
				Pair<String, String> parentPair = vparents.get(i);
				//	find until root
				while(!parentPair.getSecond().equals(NIL))
				{
					for(int j = 0; j < vparents.size(); ++j)
					{
						if(vparents.get(j).getFirst().equals(parentPair.getSecond()))
						{
							parentPair = vparents.get(j);
							break;
						}
					}
				}
				//	put into right cluster
				String parent = parentPair.getFirst();
				for(int j = 0; j < clusters.length; ++j)
				{
					if(parent.equals(clusters[j].get(0)))
					{
						clusters[j].add(current);
						break;
					}
				}
			}
		}
		
		//	distance between each cluster center to the target tag
		double[] distances = new double[m_EnsembleClusterNumber];
		
		//	set target
		Vector<Double> target = new Vector<Double>();
		for(int i = 0; i < m_Sequence.length; ++i)
		{
			target.add(1.0);
		}
		//	calculate distance
		Distance distFunc = new EuclideanDistance();
		for(int i = 0; i < clusters.length; ++i)
		{
			distances[i] = 0.0;
			for(int j = 0; j < clusters[i].size(); ++j)
			{
				String label = clusters[i].get(j);
				Vector<Double> v = new Vector<Double>();
				Vector<Double> tmp = m_Set.getRecordByKeys(label);
				for(int k = 0; k < m_Sequence.length; ++k)
				{
					v.add(tmp.get(m_Sequence[k] - 1));
				}
				distances[i] += distFunc.distance(target, v) / clusters[i].size();
			}
		}
		
		//	sort according to distance
		for(int i = 0; i < clusters.length - 1; ++i)
		{
			for(int j = clusters.length - 1; j > 0; --j)
			{
				if(distances[j] < distances[j - 1])
				{
					double tmp = distances[j];
					distances[j] = distances[j - 1];
					distances[j - 1] = tmp;
					Vector<String> tmpV = clusters[j];
					clusters[j] = clusters[j - 1];
					clusters[j - 1] = tmpV;
				}
			}
		}
		//	output test
/*		System.out.println("For target tag '" + m_Set.getTargetTag() + "':");
		for(int i = 0; i < clusters.length; ++i)
		{
			System.out.println("For cluster " + i + ":");
			for(String tag : clusters[i])
			{
				System.out.print(tag + "\t");
			}
			System.out.println();
		}*/
		
		for(int i = 0; i < m_EnsembleClusters.length; ++i)
		{
			m_EnsembleClusters[i] = clusters[i];
		}
		
		return m_EnsembleClusters;
	}
	
	
	public String toString()
	{
		String msg = new String();
		
		return msg;
	}
	
	public static void main(String[] args)
	{
		int sequence[] = {1,2,3,4,5,6,7,8};
		int numOfCandidateTags = 5;
		int recordsForEachTag = 30;
		//int numOfCluster = 4;
		int numOfCluster = (int)Math.sqrt(recordsForEachTag);
		int ensembleCluster = 4;
		
		PreProcess preProcess = new PreProcess(numOfCandidateTags, sequence, recordsForEachTag);
		SimilaritySet set[] = preProcess.preProcess();
		ClusterEnsemble ensemble = new ClusterEnsemble(set[3], sequence, set[3].getKeys(), ensembleCluster);
		Distance dist = new EuclideanDistance();
		Clusterer[] kmeans = new Clusterer[3];
		for(int i = 0; i < kmeans.length; ++i)
		{
			kmeans[i] = new KMeans(sequence, numOfCluster, set[3], set[3].getKeys(), dist);
			ensemble.addClusterer(kmeans[i]);
		}
		ensemble.doEnsemble();
	}
	
}
